#include "tool.h"
#include <iostream>

using std::cin;
using std::cout;
using std::endl;
using namespace tool;

tool::Graph* Graph::killRing(Map &out){
	int *time = new int[n], ip = 0;
	UnionFindSet ufs(n);

	resetVisit();
	// 对正向边dfs,按离开时间排序
	for (int i = 0; i < n; ++i)
		if (!visit[i]) dfs(i, [time, &ip](int cur){time[ip++] = cur;});

	// 反向边
	reverse();
	resetVisit();
	for (int i = n-1; i >= 0; --i){
		int cur = time[i];
		if (!visit[cur]) dfs(cur, [cur, &ufs](int dst){	ufs.merge(cur, dst);});
	}

	reverse();

	ip = 0;
	std::map<int ,int> map;
	for (int i = 0; i < n; ++i)
		if (ufs.find(i) == i) map[i] = ip++;

	out.assign(ip, std::set<int>());

	for (int i = 0; i < n; ++i)
		out[map[ufs.find(i)]].insert(i);

	Graph *ret = new Graph(ip);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (edge(i,j))
				ret->setEdge(map[ufs.find(i)], map[ufs.find(j)]);

	delete []time;
	return ret;
}

void tool::Graph::display(const Map &map){
	for (size_t i = 0; i < map.size(); ++i){
		std::cout << i << " :" << std::endl;
		for (std::set<int>::const_iterator iter = map[i].begin();
				iter != map[i].end(); ++i)
			std::cout << *iter << ' ';
		std::cout << std::endl;
	}
}

void tool::Graph::closure(){
	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				edge(i,j) |= edge(i,k)&edge(k,j);
}

void tool::Graph::foreach(std::function<void(int,int)> func){
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			func(i,j);
}


















